package de.infotheo;

import java.math.BigInteger;
import java.util.Vector;

/**
 * The class BabyStepGiantStep contains a method to calculate a discrete
 * logarithm by the baby step giant step algorithm
 * 
 * @author Eugen
 * 
 */
public class BabyStepGiantStep {

	/**
	 * The method calcDiscLog calculates the discrete logarithm to determine the
	 * result of h = log_g modulo group order
	 * 
	 * @param groupElement
	 *            the base of logarithm
	 * @param groupZ
	 *            the group containing the g
	 * @param h
	 *            the result of g^x
	 * 
	 * @return x
	 */
	public BigInteger calcDiscLog(BigInteger groupElement, BigInteger groupZ,
			BigInteger h) {

		// initiation of needed objects and parameters

		BigInteger m = new BigInteger("0");
		BigInteger res = new BigInteger("0");
		OrderOfGroupMember ordE = new OrderOfGroupMember();
		Vector<BigInteger> babySet = new Vector<BigInteger>();
		boolean breakFlag = false;
		// determining the order of groupElement in groupZ
		BigInteger orderOfElement = ordE.calcOrderOfGroupMember(groupElement,
				groupZ);

		// calculating the rounded up root of the group order of orderOfElement
		// to determine m which is needed as iteration parameter
		m = new BigInteger(Double
				.toString(
						Math.ceil(Math.sqrt(Double.parseDouble(orderOfElement
								.toString())))).replaceAll("\\.0", "").trim());

		System.out.println("m = " + m.toString());

		// iteration of r from 0 to m while calculating the baby set elements
		// h*g^(-r) | break when an element of baby set is 1 | if not break,
		// then calculate (g^m)^j where j goes from 0 to m and compare the
		// result with the elements of the baby set
		for (BigInteger r = new BigInteger("0"); r.compareTo(m) == 0
				|| r.compareTo(m) == -1; r = r.add(new BigInteger("1"))) {

			babySet.add(h.multiply(
					groupElement.modInverse(groupZ).modPow(r, groupZ)).mod(
					groupZ));

			System.out.println("r = " + r.toString() + "  h*g^(-r) = "
					+ babySet.get(Integer.parseInt(r.toString())));
			// if 1 is element of baby step set, then is r the result of the
			// algorithm and the function returns r
			if (Integer.parseInt(babySet.get(Integer.parseInt(r.toString()))
					.toString()) == 1) {

				res = r;
				breakFlag = true;
			}
		}
		if (!breakFlag) {

			for (BigInteger j = new BigInteger("0"); j.compareTo(m) == 0
					|| j.compareTo(m) == -1; j = j.add(new BigInteger("1"))) {

				BigInteger tempRes = groupElement.modPow(m, groupZ);
				tempRes = tempRes.modPow(j, groupZ);

				System.out.println("j = " + j.toString() + "  (g^m)^j = "
						+ tempRes);
				// compare the elements of the baby step set with the the result
				// of (g^m)^j and if equal compute j * m + r
				for (BigInteger bigInteger : babySet) {

					if (tempRes.compareTo(bigInteger) == 0) {

						res = j.multiply(m)
								.add(new BigInteger(Integer.toString(babySet
										.indexOf(bigInteger)))).mod(groupZ);
						breakFlag = true;
						break;
					}
				}
				if (breakFlag) {
					break;
				}
			}
		}
		System.out.println("log_" + groupElement.toString() + " "
				+ h.toString() + " mod " + groupZ.toString() + " = "
				+ res.toString());

		// verification of the result
		BigInteger verRes = groupElement.modPow(res, groupZ);
		System.out.println("Verification: " + groupElement.toString() + "^("
				+ res.toString() + ") mod " + groupZ + " = "
				+ verRes.toString());

		int comp = h.compareTo(verRes);
		if (comp == 0) {

			System.out.println("Result correct :-)");

		} else {
			System.out.println("Result incorrect :-(");
			if (Integer.parseInt(res.toString()) == 0) {

				System.out.println("No match with set B!");
			}
		}
		return res;
	}
}
